# -*- coding: utf-8 -*-
#--------------------------------------------------------------------------
# Copyright (c) 2009 Barry Schwartz
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.

#--------------------------------------------------------------------------

class nibbletrie(object):

    def __init__(self, nibble_size = 4):
        self.nibble_size = nibble_size
        self.block_size = 2 ** nibble_size
        self.keys = [None for i in range(self.block_size)]
        self.values = [None for i in range(self.block_size)]

    def add(self, key, value):

        '''The keys have to be non-negative integers.'''

        offset = 0
        nibble = key & (self.block_size - 1)
        key >>= self.nibble_size

        while key != 0:
            if self.keys[offset + nibble] is None:
                new_offset = len(self.keys)
                self.keys[offset + nibble] = new_offset
                offset = new_offset
                self.keys += [None for i in range(self.block_size)]
                self.values += [None for i in range(self.block_size)]
            else:
                offset = self.keys[offset + nibble]

            nibble = key & (self.block_size - 1)
            key >>= self.nibble_size

        self.values[offset + nibble] = value

    def get(self, key):

        offset = 0
        nibble = key & (self.block_size - 1)
        key >>= self.nibble_size

        while key != 0 and self.keys[offset + nibble] is not None:
            offset = self.keys[offset + nibble]
            nibble = key & (self.block_size - 1)
            key >>= self.nibble_size

        return None if key != 0 else self.values[offset + nibble]



#?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
p = [
    (0, 0),
    (1, 1),
    (3, 3),
    (2, 2),
]
"""
    (5, 5),
    (10, 10),
    (3, 3),
    (20, 20),
    (12, 12),
    (1080, 1080),
    (120, 120),
    (12000000, 12000000),
    ]
"""

nt = nibbletrie()
for (k, v) in p:
    nt.add(k, v)
print(nt.keys)
print(nt.values)
#for (k, v) in p + [(50, 50)]:
for (k, v) in p:
    print(repr(nt.get(k)))
#?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
